115. Distinct Subsequences

https://leetcode.com/problems/distinct-subsequences/

題目解釋

你會得到字串s和t，請從字串s中的所有字母，找出有幾種組合能組成字串t

example

解法

• 今天來不及解，明天補上，預估會用回朔法吧
• 9/20補上

一開始的想法是用回朔法把所有可行的組合找出來，但是時間超過系統要求(Time Limit Exceeded)，想法如下

1. 先列出字串s中所有組成t所需的字母位置，以example2為例:
   {b:[0,2,4]}、{a:[1,5]}、{g:[3,6]}

2. 接著，從b挑出一個位置i、a挑出一個大於i的位置j、g挑出一個大於j的位置k

3. 重複幾次找出i, j, k的動作並組合: [0, 1, 3]、[0, 1, 5]、[0, 5, 6]、[2, 5, 6]、[4, 5, 6]

程式碼

class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        
        s_dict = defaultdict(list)
        
        for i in range(len(s)):
            s_dict[s[i]].append(i)
        
        
        def backtracking(level, previ, memo):
            
            if (level, previ) in memo:
                return  memo[(level, previ)]
            
            if level == len(t):
                return 1
            
            ans = 0
            for i in s_dict[t[level]]:
                
                if previ < i:

                    ans += backtracking(level+1, i, memo)
                    memo[(level, previ)] = ans
            
            return ans
        
        
        return backtracking(0, -1, {})

可通過的解法

第二個解法則是看別人答案來的，先看看程式碼吧

程式碼

class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        
        @cache
        def dp(i, j):
            
            if j == len(t):
                return 1
            
            if i == len(s):
                return 0
            
            if len(s) - i < len(t) - j:
                return 0
            
            
            if s[i] == t[j]:
                return dp(i+1, j+1) + dp(i+1, j)
            
            return dp(i+1, j)
        
        return dp(0, 0)

這個方法則是從兩個字串的第一個字母開始比對，我們先看看下面這部分，並同樣以example2當例子

if s[i] == t[j]:
    return dp(i+1, j+1) + dp(i+1, j)
return dp(i+1, j)

return dp(i+1, j+1) + dp(i+1, j)我們分別來看這兩個遞迴的意思

1. dp(i+1, j+1): 如果兩個字母相同(找到b)，我們就找下組成字串t需要的字母(找a)
2. dp(i+1, j): 就算兩個字母相同，我們也當成不需要他，再次去尋找同樣目標(找其他位置的b)

下面這段也很重要，可以節省很多時間，意思是s剩下的長度比t剩下的程度還短的話，就不可能組出t了

if len(s) - i < len(t) - j:
    return 0

最後，@cache要記得加上去，他是叫你的cache採用LRU策略，沒加的話過不了

閒聊

大家中秋快樂